package daily.year2024.m8;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class d25 {
    class Solution1 {
        public int[] asteroidCollision(int[] asteroids) {
            int n = asteroids.length;
            ArrayDeque<Integer> queue = new ArrayDeque<>();
            List<Integer> negative = new ArrayList<>();
            for(int i=0;i < n;i++) {
                if(asteroids[i] < 0) {
                    while(!queue.isEmpty() && asteroids[queue.getLast()] < -asteroids[i]) {
                        queue.pollLast();
                    }
                    if(!queue.isEmpty()) {
                        if(asteroids[queue.getLast()] == -asteroids[i]) {
                            queue.pollLast();
                        } else if(asteroids[queue.getLast()] < -asteroids[i]) {
                            negative.add(i);
                        }
                    } else {
                        negative.add(i);
                    }
                } else {
                    queue.add(i);
                }
            }
            //合并两个集合
            int size = queue.size() + negative.size();
            int[] res = new int[size];
            int l = 0, nl = 0;
            while(!queue.isEmpty() && nl < negative.size()) {
                if(queue.peek() < negative.get(nl)) {
                    res[l] = asteroids[queue.poll()];
                } else {
                    res[l] = asteroids[negative.get(nl)];
                    nl++;
                }
                l++;
            }
            while(!queue.isEmpty()) {
                res[l] = asteroids[queue.poll()];
                l++;
            }
            while(nl < negative.size()) {
                res[l] = asteroids[negative.get(nl)];
                nl++;
                l++;
            }
            return res;
        }
    }
}
